Homework 1

Consider a graph search from S to G on the graph below. Edges are labeled with action costs. Assume that ties are broken alphabetically (so a partial plan S->X->A would be expanded before S->X->B and S->A->Z would be expanded before S->B->A.)

Which search strategy will return the path S-B-G?

Continue with Graph Search Part 2, which search strategy will return the path S-A-D-E-G?

Consider uniform cost graph search from S to G on the graph below. Arcs are labeled with action costs. Assume that ties are broken alphabetically (so a partial plan S->X->A would be expanded before S->X->B and S->A->Z would be expanded before S->B->A.

Rank the nodes according to the visiting sequence during uniform cost search.

Note: nodes visited during UCS might not be included in the path returned by UCS.

Given the heuristic for each node. Consider A* search from S to G on the graph below. Arcs are labeled with action costs. Assume that ties are broken alphabetically (so a partial plan S->X->A would be expanded before S->X->B and S->A->Z would be expanded before S->B->A.

Choose the path returned by A* search.

Given another heuristic assignment for each node. Consider A* search from S to G on the graph below. Arcs are labeled with action costs. Assume that ties are broken alphabetically (so a partial plan S->X->A would be expanded before S->X->B and S->A->Z would be expanded before S->B->A.

The heuristic violates admissibility and consistency. Change the heuristic of only one node to make the heuristic meet admissibility and consistency.

You control one or more insects in a rectangular maze-like environment with dimensions M*N, as shown in the figure below.

At each time step, an insect can move into an adjacent square if that square is currently free, or the insect may stay in its current location. Squares may be blocked by walls, but the map is known. Optimality is always in terms of time steps; all actions have cost 1 regardless of the number of insects moving or where they move.

For each question, you should answer for a general instance of the problem, not simply for the example maps shown.

You control a single insect as shown in the maze below, which must reach a designated target location X, also known as the hive. There are no other insects moving around.

Which of the following is a minimal correct state space representation?

Only in this question, suppose there is a pellet somewhere in the maze (not on the walls). Before reaching the designated location X, the insect must eat this pellet.

By adding this assumption, please give a tight upper bound on the size of the state space.

You control a single insect as shown in the maze below, which must reach a designated target location X, also known as the hive. There are no other insects moving around.

Which of the following heuristics are admissible (if any)?

Recall from lecture the general algorithm for GRAPH-SEARCH reproduced below.

With the above implementation a node that reaches a goal state may sit on the fringe while the algorithm continues to search for a path that reaches a goal state. Let's consider altering the algorithm by testing whether a node reaches a goal state when inserting into the fringe. Concretely, we add the line of code highlighted below:

Now, we've produced a graph search algorithm that can find a solution faster. However, In doing so we might have affected some properties of the algorithm. To explore the possible differences, consider the example graph below.

If using EARLY-GOAL-CHECKING-GRAPH-SEARCH with an A* node expansion strategy, which path, if any, will the algorithm return?

Assume you run EARLY-GOAL-CHECKING-GRAPH-SEARCH with the A* node expansion strategy and a consistent heuristic, select all statements that are true.

You are asked to determine the layout of a new, small college. The campus will have four structures: an administration structure (A), a bus stop (B), a classroom (C), and a dormitory (D). Each structure (including the bus stop) must be placed somewhere on the grid shown below.

The layout must satisfy the following constraints:

1. The bus stop (B) must be adjacent to the road.
2. The administration structure (A) and the classroom (C) must both be adjacent to the bus stop (B).
3. The classroom (C) must be adjacent to the dormitory (D).
4. The administration structure (A) must not be adjacent to the dormitory (D).
5. The administration structure (A) must not be on a hill.
6. The dormitory (D) must be on a hill or adjacent to the road.
7. All structures must be in different grid squares.

Here, adjacent means that the structures must share a grid edge, not just a corner.

Which of the constraints above are unary constraints?

1. The bus stop (B) must be adjacent to the road.
2. The administration structure (A) and the classroom (C) must both be adjacent to the bus stop (B).
3. The classroom (C) must be adjacent to the dormitory (D).
4. The administration structure (A) must not be adjacent to the dormitory (D).
5. The administration structure (A) must not be on a hill.
6. The dormitory (D) must be on a hill or adjacent to the road.
7. All structures must be in different grid squares.

Select the domains of all variables after unary constraints have been applied.

The layout must satisfy the following constraints:

1. The bus stop (B) must be adjacent to the road.
2. The administration structure (A) and the classroom (C) must both be adjacent to the bus stop (B).
3. The classroom (C) must be adjacent to the dormitory (D).
4. The administration structure (A) must not be adjacent to the dormitory (D).
5. The administration structure (A) must not be on a hill.
6. The dormitory (D) must be on a hill or adjacent to the road.
7. All structures must be in different grid squares.

Let's start from the answer to Part 2(in which unary constraints are enforced) and enforce arc consistency. Initally, the queue contains all arcs (in alphabetical order). Select the domains of all variables after Arightwards arrow B is enforced.

The layout must satisfy the following constraints:

1. The bus stop (B) must be adjacent to the road.
2. The administration structure (A) and the classroom (C) must both be adjacent to the bus stop (B).
3. The classroom (C) must be adjacent to the dormitory (D).
4. The administration structure (A) must not be adjacent to the dormitory (D).
5. The administration structure (A) must not be on a hill.
6. The dormitory (D) must be on a hill or adjacent to the road.
7. All structures must be in different grid squares.

You can verify that enforcing consistency for AC, AD, BA, BC, BD, and CA do not change the domains of any variables. After enforcing these arcs, the next is CB.

Continuing from the previous parts, select the domains of all variables after CB is enforced.

The layout must satisfy the following constraints:

1. The bus stop (B) must be adjacent to the road.
2. The administration structure (A) and the classroom (C) must both be adjacent to the bus stop (B).
3. The classroom (C) must be adjacent to the dormitory (D).
4. The administration structure (A) must not be adjacent to the dormitory (D).
5. The administration structure (A) must not be on a hill.
6. The dormitory (D) must be on a hill or adjacent to the road.
7. All structures must be in different grid squares.

Continuing from the previous parts, select the domains of all variables after enforcing arc consistency until the queue is empty. Remember that the queue currently contains CD, DA, DB, DC, and any arcs that were added while enforcing CB.

The layout must satisfy the following constraints:

1. The bus stop (B) must be adjacent to the road.
2. The administration structure (A) and the classroom (C) must both be adjacent to the bus stop (B).
3. The classroom (C) must be adjacent to the dormitory (D).
4. The administration structure (A) must not be adjacent to the dormitory (D).
5. The administration structure (A) must not be on a hill.
6. The dormitory (D) must be on a hill or adjacent to the road.
7. All structures must be in different grid squares.

Arc consistency had resulted in domains having more than one single value left. In order to solve the problem, we need to start searching. Use the MRV (minimum remaining values) heuristic to choose which variable gets assigned next (breaking any ties alphabetically).

Which variable gets assigned next?

The layout must satisfy the following constraints:

1. The bus stop (B) must be adjacent to the road.
2. The administration structure (A) and the classroom (C) must both be adjacent to the bus stop (B).
3. The classroom (C) must be adjacent to the dormitory (D).
4. The administration structure (A) must not be adjacent to the dormitory (D).
5. The administration structure (A) must not be on a hill.
6. The dormitory (D) must be on a hill or adjacent to the road.
7. All structures must be in different grid squares.

The variable you selected should have two values left in its domain. We will use the least-constraining value (LCV) heuristic to decide which value to assign before contuing with the search. To choose which value is the least-constraining value, enforce arc consistency for each value (on a scratch piece of paper). For each value, count the total number of values remaining over all variables.

Which value has the largest number of values remaining (and therefore is the least constraining value)?

Consider the following tree-structured CSP that encodes a coloring problem in which neighboring nodes cannot have the same color. The domains of each node are shown.

The algorithm for solving tree-structured CSPs starts by picking a root variable. We can pick any variable for this. For this exercise, we will pick A. There are several linearizations consistent with A as the root; we will use the one shown below.

Step 1: Remove Backward

In this step we start with the right-most node (E), enforce arc-consistency for its parent (B),then do the same for the second-to-right-most node (C) and its parent (B), and so on. Execute this process, and then mark the remaining values for each variable below.

Step 2: Assign Forward

Now that all domains have been pruned, we can find the solution in a single forward pass (i.e. no need for backtracking). This is done by starting at the left-most node (A), picking any value remaining in its domain, then going to the next variable (B), picking any value in its domain that is consistent with its parent, and continue left to right, always picking a value consistent with its parent’s assignment.

If at any given node there are multiple colors left that are consistent with its parent’s value, break ties by picking red over green, and then green over blue.

What is the solution found by running the algorithm?

Your company plans to purchase a new computer for you. However, your company has recently suffered from budget deficit, so the manager wants to spend as little money as possible. The retailer always wants to sell the most expensive model. You don't want to take sides so you decide to pick at random. All prices (including X and Y) are assumed to be nonnegative.

We know that Y is at most $90. What values of X will result in the computer from Apple regardless of the exact price of Y?

The upper bound of X (not including):

Assume we run α-β pruning, expanding successors from left to right, on a game with trees as shown below.

Choose all the nodes which can be pruned.